#ifndef PROGRAM_DATASTRUCT_BINARY_SEARCH_TREE_H_
#define PROGRAM_DATASTRUCT_BINARY_SEARCH_TREE_H_
namespace binarysearchtree{

#define DEFAULT_SEARCH_TREE_CAP 10

class BinarySearchNode
{
public:
    BinarySearchNode();
public:
    void SetData(int d);
    void SetParent(BinarySearchNode* p);
    void SetLeft(BinarySearchNode* l);
    void SetRight(BinarySearchNode* r);

    int GetData();
    BinarySearchNode* GetParent();
    BinarySearchNode* GetLeft();
    BinarySearchNode* GetRight();
private:
    int m_data;
    BinarySearchNode* m_parent;
    BinarySearchNode* m_left;
    BinarySearchNode* m_right;
};

class BinarySearchTree
{
public:
    BinarySearchTree(int cap);
    ~BinarySearchTree();
public:
    void InsertData(int d);
    void DelData(int d);
    BinarySearchNode* FindData(int d);
    void Inorder();
    int MinValue();
    int MaxValue();
private:
    BinarySearchNode* Min(BinarySearchNode* n);
    BinarySearchNode* Max(BinarySearchNode* n);
    void inorderhelper(BinarySearchNode* n);
    void transplant(BinarySearchNode* u, BinarySearchNode* v);
    BinarySearchNode* Successor(BinarySearchNode* n );
    BinarySearchNode* Predecessor(BinarySearchNode* n );
private:
    BinarySearchNode* m_root;
    BinarySearchNode* m_content;
    int m_size;
    int m_cap;
};


}

#endif // PROGRAM_DATASTRUCT_BINARY_SEARCH_TREE_H_
